'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-04 10:39:28
'''
'''
32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
'''
from typing import List

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        re = 0
        for i, v in enumerate(s):
            if v == '(':
                stack.append((v, i))
            else:
                if stack:
                    # print('haha', stack)
                    tmp = stack[-1]
                    if tmp[0] == '(':
                        stack.pop()
                        tmp_ind = -1
                        if stack:
                            tmp_ind = stack[-1][1]
                        # print(stack,tmp_ind)
                        re = max(re, i-tmp_ind)                        
                    else:
                        stack.append((v, i))
                else:
                    stack.append((v, i))
        return re
if __name__ == "__main__":
    solution = Solution()
    s = ")()())"
    print(solution.longestValidParentheses(s))